#include <iostream>
#include <cassert>
#include "heap.h"
using namespace std;


void shiftDown(int* heap, int size, int curIdx)
{
	int childIdx;
	int tmp = heap[curIdx];
	for (; (curIdx << 1) <= size; curIdx = childIdx )
	{
		childIdx = (curIdx << 1);
		if ( childIdx != size && heap[childIdx] > heap[childIdx+1] )
			++ childIdx;
		if ( tmp > heap[childIdx] )
			heap[curIdx] = heap[childIdx];
		else
			break;
	}
	heap[curIdx] = tmp;
}

int deleteMin (int* heap, int& size)
{
	assert(size != 0);
	int ret = heap[1];
	heap[1] = heap[size--];
	shiftDown(heap, size, 1);
	return ret;
}

void buildHeap (int* heap, int size)
{
	int i;
	for (i = size/2; i > 0; i --)
		shiftDown(heap, size, i);
}

void insert(int* heap, int& size, int data)
{
	assert(size < MAX_HEAP_SIZE);
	int curIdx = ++ size;
	for (; curIdx > 1; curIdx >>= 1 )
	{
		if ( heap[curIdx>>1] > data )
			heap[curIdx] = heap[curIdx>>1];
		else
			break;
	}
	heap[curIdx] = data;
}

void printHeap(int* heap, int size)
{
	int i;
	for (i = 1; i <= size; i ++)
		printf("%d ", heap[i]);
	putchar('\n');
}